package cn.javadog.algorithm.e101_200;

import java.util.LinkedList;


/**
 * 填充每个节点的下一个右侧节点指针
 * https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
 * @author Sprite
 * @date
 */
public class Algorithm116 {

	public Node connect(Node root) {
		if(root==null) return root;
		LinkedList<Node> queue = new LinkedList<>();
		queue.add(root);
		while(!queue.isEmpty()) {
			int len = queue.size();
			Node next = null;
			for(int i=0; i<len; i++) {
				Node cur = queue.poll();
				if(cur.right!=null) queue.add(cur.right);
				if(cur.left!=null) queue.add(cur.left);
				cur.next = next;
				next = cur;
			}
		}
		return root;

	}

	static class Node {
		public int val;
		public Node left;
		public Node right;
		public Node next;
	}

}

